package _18_剑指OfferII;


import _18_剑指OfferII.datastrcute.ListNode;

import java.util.List;

public class _077_剑指OfferII链表排序 {

    public static void main(String[] args) {

        _077_剑指OfferII链表排序 v = new _077_剑指OfferII链表排序();

        ListNode first = new ListNode(4);
        ListNode second = new ListNode(2);
        first.next = second;
        ListNode three = new ListNode(1);
        second.next = three;
        ListNode four = new ListNode(3);
        three.next = four;

        ListNode listNode = v.sortList(first);

        while (listNode != null) {
            System.out.println(listNode.val);
            listNode = listNode.next;
        }

    }

    private ListNode mergeListNode(ListNode leftPart, ListNode rightPart) {
        ListNode result = new ListNode(-1);
        ListNode dummy = result;

        while (leftPart != null && rightPart != null) {
            if (leftPart.val < rightPart.val) {
                dummy.next = leftPart;
                leftPart = leftPart.next;
            } else {
                dummy.next = rightPart;
                rightPart = rightPart.next;
            }
            dummy = dummy.next;
        }
        if (leftPart != null) {
            dummy.next = leftPart;
        } else if (rightPart != null) {
            dummy.next = rightPart;
        }
        return result.next;
    }

    // 基于归并排序，每次使用双指针查找中间节点, 自顶向下，存在log(n)的空间复杂度
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) return head;

        ListNode mid = split(head);

        ListNode leftPart = sortList(head);

        ListNode rightPart = sortList(mid);

        return mergeListNode(leftPart, rightPart);
    }

    // 根据节点，分割为头节点，和中间节点
    private ListNode split(ListNode head) {
        ListNode preSlow = null;
        ListNode slow = head;
        ListNode fast = slow;
        while (fast != null && fast.next != null) {
            preSlow = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        if (preSlow != null) preSlow.next = null;
        // 断开链表
        return slow;
    }

}
